//Given n non-negative integers representing an elevation map where the width of
// each bar is 1, compute how much water it is able to trap after raining. 
//
// 
//The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In 
//this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos
// for contributing this image! 
//
// Example: 
//
// 
//Input: [0,1,0,2,1,0,1,3,2,1,2,1]
//Output: 6 
// Related Topics 栈 数组 双指针

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    fun trap(height: IntArray): Int {
        var result = 0
        val stack = java.util.Stack<Int>()
        for (i in height.indices) {
            while (!stack.empty() && height[i] > height[stack.peek()]) {
                val top = stack.pop()
                if(stack.empty()){
                    break
                }
                val distance = i - stack.peek() - 1
                val offsetHeight = Math.min(height[i], height[stack.peek()]) - height[top]
                result += distance * offsetHeight
            }
            stack.push(i)
        }
    return result
    }
}

//leetcode submit region end(Prohibit modification and deletion)
